package ListNode;

public class ex_230514 {
    // 判断链表中是否有环
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        // 快慢指针
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    // 链表中环的入口结点
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }

        // 快慢指针
        ListNode slow = pHead;
        ListNode fast = pHead;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 首次相遇后
                // 让一个指向头结点
                // 两个指针相同速率走
                // 再次相遇时, 就在入口结点上
                fast = pHead;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    // 链表中倒数最后k个结点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if (pHead == null) {
            return null;
        }
        ListNode first = pHead;

        for (int i = 0; i < k; i++) {
            if (first == null) {
                // 长度不够 k 个
                return null;
            }
            // 要放在判空后面,
            // 放在前面的话, 如果长度刚好为k个, 就会返回null
            first = first.next;
        }

        ListNode second = pHead;

        while (first != null) {
            first = first.next;
            second = second.next;
        }
        return second;
    }

    // 删除链表的倒数第n个节点
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // 题目保证 n 一定是有效的
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        ListNode slow = head;
        ListNode pre = null;
        while (fast != null) {
            pre = slow;
            fast = fast.next;
            slow = slow.next;
        }

        if (pre == null) {
            // pre 为 null, 说明要删除的结点就是第一个结点
            return head.next;
        }

        pre.next = slow.next;

        return head;
    }

    // 两个链表的第一个公共结点
    // 方法1, 计算两个链表长度
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        ListNode node1 = pHead1;
        ListNode node2 = pHead2;
        int len1 = 0;
        while (node1 != null) {
            node1 = node1.next;
            len1++;
        }
        int len2 = 0;
        while (node2 != null) {
            node2 = node2.next;
            len2++;
        }

        // 让 node1 遍历长的链表
        if (len1 > len2) {
            node1 = pHead1;
            node2 = pHead2;
        } else {
            node1 = pHead2;
            node2 = pHead1;
        }

        // len1 - len2 取绝对值
        for (int i = 0; i < Math.abs(len1 - len2); i++) {
            node1 = node1.next;
        }
        while (node1 != node2) {
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }

    // 方法2, 两个指针分别遍历一次链表1和链表2
    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        ListNode node1 = pHead1;
        ListNode node2 = pHead2;
        while (node1 != node2) {
            // 如果为null, 就指向另一个链表头结点
            node1 = node1 == null ? pHead2 : node1.next;
            node2 = node2 == null ? pHead1 : node2.next;
        }
        return node1;
    }
}
